package performance;

import java.util.ArrayList;
import java.util.Random;
import java.util.Stack;

public class QuickSort_NoRec_AllImproved {
	public static int THRESHOLD = 12;
	public static Random pivotRandom = new Random();
	static 
	{
		pivotRandom.setSeed(System.currentTimeMillis());
	}
	public static int selectPivot(int left, int right)
	{
//		return (left + right) / 2;
		int pivot = Math.abs(pivotRandom.nextInt()) % (right - left) + left;
		return pivot;
	}
	public static int partition(ArrayList<Double> des, int left, int right ,int pivot)
	{
		double temp = des.get(pivot);
		des.set(pivot, des.get(right));
//		des.set(right, temp);
		int i = left;
		int j = right;
		while( i != j)
		{
			while (des.get(i) < temp && i < j)
				i++;
			if (i < j)
			{
				des.set(j, des.get(i));
				j --;
			}
			while (des.get(j) > temp && i < j)
				j --;
			if (i < j)
			{
				des.set(i, des.get(j));
				i ++;
			}
		}
		des.set(i, temp);
		return i;
	}
	public static void qsort(ArrayList<Double> a, int left, int right)
	{
		Stack<BoardStruct> boardStack = new Stack<BoardStruct>();
		BoardStruct oneBoard = new BoardStruct(left, right);
		boardStack.add(oneBoard);
		
		while(! boardStack.isEmpty())
		{
			BoardStruct thisBoard = boardStack.pop();
			if (thisBoard.left >= thisBoard.right)
			{
				continue;
			}
			else if (thisBoard.right - thisBoard.left + 1 <= THRESHOLD)
			{
				for (int i=thisBoard.left + 1; i<= thisBoard.right; i++)
				{
					double temp = a.get(i);
					int j = i - 1;
					while (j >= thisBoard.left && a.get(j) > temp)
					{
						a.set(j + 1, a.get(j));
						j = j - 1;
					}
					a.set(j + 1, temp);
				}
				continue;
			}
			int pivot = selectPivot(thisBoard.left, thisBoard.right);
			pivot = partition(a, thisBoard.left, thisBoard.right, pivot);
			BoardStruct leftBoard = new BoardStruct(thisBoard.left, pivot - 1);
			boardStack.push(leftBoard);
			BoardStruct rightBoard = new BoardStruct( pivot + 1, thisBoard.right);
			boardStack.push(rightBoard);
		}
	}
	public static void main(String args[])
	{
		for (int j = 8; j<=16; j++)
		{
			ArrayList<Double> a = new ArrayList<Double>();
			THRESHOLD = j;
			Random random = new Random();
			for (int i=0; i<1000000; i++)
			{
				a.add(random.nextDouble());
			//	a.add((double)i);
			}
			long start = System.currentTimeMillis();
			qsort(a, 0, a.size()-1);
			long end = System.currentTimeMillis();
			System.out.println((end - start));
			for (int i=0; i<a.size(); i++)
			{
			//	System.out.println((i+1) + ": " +  a.get(i));
				if (i > 0)
				{
					if (a.get(i-1) > a.get(i))
					{
						System.out.println("Wrong");
						break;
					}
				}
			}
		}
	}
}
